package ink.lovejinhu.swardToOffer;

public class Offer_063 {


    /**
     *
     *  假设第i天卖出第收益为f(i)
     *
     *  f(i)=f(i-1)
     *
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {

        int maxProfix = 0;
        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                if (prices[j]-prices[i]>maxProfix){
                    maxProfix=prices[j]-prices[i];
                }
            }
        }
        return maxProfix;
    }

    public int maxProfit1(int[] prices) {
        if (prices.length==0){
            return 0;
        }
        int[] ints = new int[prices.length+1];
        ints[0]=0;
        ints[1]=0;
        int days=0;
        for (int i = 1; i <prices.length ; i++) {
            ints[i+1]=Math.max(ints[i],prices[i]-prices[days]);
            if (prices[i]<prices[days]){
                days=i;
            }
        }
        return ints[prices.length];
    }
}
